package com.dynasty;

/**
 * @description Created by wangchao12 on 2019/5/20 16:46.
 */

public class Sort {
    public void swap(int[] array, int i, int j) {
        /** 方法一 **/
        //int temp = array[j];
        //array[j] = array[j + 1];
        //array[j + 1] = temp;

        /** 方法二 **/
        //array[j] = array[j] + array[j + 1];
        //array[j + 1] = array[j] - array[j + 1];
        //array[j] = array[j] - array[j + 1];

        /** 方法三 **/
        array[i] = array[i] ^ array[j];
        array[j] = array[i] ^ array[j];
        array[i] = array[i] ^ array[j];
    }

    /**
     * 方法的功能描述：冒泡排序
     * 将序列中所有元素两两比较，将最大的放在最后面。
     * 将剩余序列中所有元素两两比较，将最大的放在最后面。
     * 重复第二步，直到只剩下一个数。
     *
     * @param
     * @return
     */
    public void bubbleSort(int[] array) {
        int length = array.length;
        for (int i = 0; i < length - 1; i++) {
            for (int j = 0; j < length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                }
            }
        }
    }

    /**
     * 方法的功能描述：直接插入排序
     * 先设定插入次数，即循环次数，for(int i=1;i<length;i++)，1个数的那次不用插入。
     *
     * @param array
     * @return
     */
    public void insertSort(int[] array) {
        int length = array.length;
        for (int i = 1; i < length; i++) {
            int j = i;
            while (j > 0 && array[j] < array[j - 1]) {
                swap(array, j, j - 1);
                j--;
            }
        }
    }

    /**
     * 方法的功能描述：简单选择排序
     *
     * @param
     * @return
     */
    public void selectSort(int[] array) {
        int length = array.length;
        for (int i = 0; i < length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < length; j++) {
                if (array[min] > array[j]) {
                    min = j;
                }
            }
            if (i != min) {
                swap(array, i, min);
            }
        }
    }

    /**
     * 方法的功能描述：快速排序
     *
     * @param
     * @return
     */
    public void quickSort(int[] array, int left, int right) {
        if (left < right) {
            int pivot = partition(array, left, right);
            quickSort(array, left, pivot - 1);
            quickSort(array, pivot + 1, right);
        }
    }

    public int partition(int[] array, int left, int right) {
        int value = array[left];
        while (left < right) {
            while (left < right && array[right] >= value) {
                right--;
            }
            if (left < right) {
                array[left++] = array[right];
            }
            while (left < right && array[left] <= value) {
                left++;
            }
            if (left < right) {
                array[right--] = array[left];
            }
        }
        array[left] = value;
        return left;
    }

    public static void main(String[] args) {
        Sort sort = new Sort();
        int[] array = new int[]{32, 43, 23, 13, 5};
        //sort.bubbleSort(array);
        //sort.insertSort(array);
        //sort.selectSort(array);
        sort.quickSort(array, 0, array.length - 1);
        sort.print(array);
    }

    /**
     * 方法的功能描述：打印数组
     *
     * @param array
     * @return
     */
    private void print(int[] array) {
        int length = array.length;
        for (int i = 0; i < length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}
